The present invention is of a method and a system for determining access to a network according to the probability of obtaining such access, and in particular to a method and a system for determining such access according to a dynamic protocol.
Networks in which many independent users share a common channel are widely spread. Examples of such networks are wireless networks, local area networks, and client-server computer networks. A key issue in these networks is the allocation of a shared channel among many competing users who wish to gain access. There are three basic strategies for shared channel acquisition which are known in the background art. The first such strategy is that of contention protocols, as in ALOHA and CSMA protocols. The second strategy includes collision-free methods, such as Time Division Multiplexing (TDM) and Frequency Division Multiplexing (FDM), while the third strategy is known as limited contention.
The basic idea of contention protocols is that users transmit whenever they have data to send. As a result, collisions are unavoidable. An example of a contention protocol is the ALOHA protocol and its many variants (for a description of ALOHA and its variants, see Tanenbaum A. S., Computer Networks, Prentice-Hall, 1996, pp. 121-124 for example, herein incorporated by reference only to teach pure ALOHA and slotted ALOHA protocols). Another example of contention is the carrier sense protocols. For carrier sense protocols, in order to reduce the likelihood of collision, users detect the state of the channel whenever they wish to transmit, but only send a message if no other user is transmitting. An example of a carrier sense protocol is the CSMA and its many variants.
Collision-free protocols divide the users into disjoint groups, such that a collision is impossible. An example of a collision-free protocol is the Time Division Multiplexing (TDM) protocol, in which each user has a dedicated time slot.
Another approach, which is a combination of the contention and the collision-free strategies, is the limited contention strategy. This strategy employs the contention protocol at periods of low loads, and a collision-free strategy at periods of high load. This is accomplished by dividing the stations into groups, which are not necessarily disjoint, such that at any given time, only one member of each group is permitted to transmit. The number of users in each group changes dynamically as a function of the load.
The contention protocols are preferable under conditions of light load, because of their low delay. As the load increases, the likelihood of collisions becomes significant, and the channel efficiency of contention protocols at high load is very poor. For example, the channel utilization of the ALOHA is very poor under high load. In order to overcome this problem, a variant of the ALOHA protocol was proposed, in which each user attempts to access the shared channel with some probability p, 0xe2x89xa6pxe2x89xa61. In comparison to the original or slotted ALOHA protocols, this method has better channel utilization under conditions of high load. However, the time delay at low load is larger. Thus, even the addition of probability access cannot overcome the inherent flaws of contention protocols.
Collision-free protocols have high delay at low load, but the channel efficiency at high load is much better then that of contention protocols. The simplest collision-free methods are TDM and FDM. These allocation schemes are efficient when the number of users is small, and the traffic is continuous. Under conditions of bursty traffic, or when the number of users is large and variable, collusion-free protocols are poor choices.
The limited contention protocols are based on collision detection capability. Namely, every collision is immediately detected by all users. Unfortunately, in some networks, such as wireless networks there is no collision detection capability: The users transmit messages through an up-link channel, and receive messages through a down-link channel. Hence, each user is only aware of collisions for messages sent by that particular user by using a time out acknowledge mechanism, but is not aware of collisions of messages from other users. These protocols are particularly impractical for satellite-based networks which have huge propagation delay and a large area covered by the network, since a user cannot always detect transmissions of other users, even when listening to the up-link channel. Listening to the down-link channel would not help because of the propagation delay. Thus, the currently available methods for sharing a limited amount of bandwidth have many drawbacks.
There is therefore a need for, and it would be useful to have, a protocol suitable for limited contention multiple access, which is efficient at conditions of both high load and low load, and which would also be suitable for satellite networks.
In the method and system of the present invention, the network channel determines a channel access probability which depends on the load of the network channel. The channel access probability is announced as a broadcast message to the users. Each user attempts to access the shared channel according to the announced probability. Thus, whenever the load on the shared channel is low, the users are requested to access the channel more often, while at loaded time periods the users wishing to access the channel may need to wait before attempting to access the network channel.
According to the present invention, there is provided a system for determining access of at least one of a plurality of users to a shared transmit channel, the shared transmit channel being shared by the plurality of users and the shared transmit channel being at least a portion of a network for connecting the plurality of users, the system comprising: (a) an access authority for determining an access probability for access by the at least one of the plurality of users according to a load on the shared transmit channel, the access probability being a probability of accessing the shared transmit channel; and (b) an access broadcaster for broadcasting the access probability to the at least one of the plurality of users, such that the at least one of the plurality of users accesses the shared transmit channel according to the access probability.
Preferably, the network is a satellite network, the access authority is a satellite, the access broadcaster is a down-link signaling channel from the satellite and the shared transmit channel includes an up-link signaling channel for transmitting a request to transmit data to the satellite.
Alternatively and preferably, the network is a cellular network, the shared transmit channel includes an up-link signaling channel, the access authority is selected from the group consisting of a mobile switching center and a base station, and the access broadcaster is the base station. More preferably, for either the cellular network or the satellite network, the at least one user attempts to transmit a Request-to-Send (RTS) message according to the access probability on the up-link signaling channel.
Also alternatively and preferably, the network is a LAN (local area network), the shared transmit channel is a bandwidth of the LAN, the access authority is a network manager and the access broadcaster is at least one address received by substantially the entirety of the plurality of users.
Also alternatively and preferably, the network is an Internet, the access authority is a Web server, the shared transmit channel is an URL for obtaining a Web page and the access broadcaster is an URL for obtaining the access probability.
Preferably, the access probability is at least partially determined according to a type of transmission being transmitted by the at least one of the plurality of users on the shared transmit channel.
Also preferably, the access probability is at least partially determined according to the at least one of the plurality of users. Also preferably, the load is determined according to an average number of transmission attempts by the plurality of users. More preferably, the access probability is determined according to the load, R, according to a previous access probability, Pcur, and according to an optimal rate of transmission attempts, Ropt. Most preferably, the access probability is determined according to an equation:             P      cur        ⁢                  R        opt            R        ⁢          xe2x80x83        ⁢    if    ⁢          xe2x80x83        ⁢    R     greater than       R    opt  
alternatively, if Rxe2x89xa6Ropt, the equation is min   min  ⁢            {                                    P            cur                    ⁢                                    R              opt                        R                          ,        1            }        .  
According to another embodiment of the present invention, there is provided a system for determining access of at least one of a plurality of users to an up-link signaling channel, the up-link signaling channel being shared by the plurality of users, the up-link signaling channel being at least a portion of a network for connecting the plurality of users, the system comprising: (a) an access authority for determining an access probability for access by the at least one of the plurality of users according to a load on the up-link signaling channel, the access probability being a probability of accessing the up-link signaling channel; and (b) a down-link signaling channel for broadcasting the access probability to the at least one of the plurality of users, such that the at least one of the plurality of users accesses the up-link signaling channel according to the access probability.
According to yet another embodiment of the present invention, there is provided a method for determining access of at least one of a plurality of users to a shared transmit channel, the shared transmit channel being shared by the plurality of users and the shared transmit channel being at least a portion of a network for connecting the plurality of users, the steps of the method being performed by a data processor and the method comprising the steps of: (a) estimating an average number of transmission attempts by the plurality of users on the shared transmit channel; (b) determining an access probability according to the average number of transmission attempts; (c) announcing the access probability to the at least one of the plurality of users; (d) receiving the access probability by the at least one of the plurality of users; and (e) accessing the shared transmit channel by the at least one of the plurality of users according to the access probability.
Hereinafter, the term xe2x80x9ccomputing platformxe2x80x9d refers to a particular computer hardware system or to a particular software operating system. Examples of such hardware systems include, but are not limited to, personal computers (PC), Macintosh(trademark) computers, mainframes, minicomputers and workstations. Examples of such software operating systems include, but are not limited to, UNIX, VMS, Linux, MacOS(trademark), DOS, one of the Windows(trademark) operating systems by Microsoft Inc. (Seattle, Wash., USA), including Windows NT(trademark), Windows 3.x(trademark) (in which xe2x80x9cxxe2x80x9d is a version number, such as xe2x80x9cWindows 3.1(trademark)xe2x80x9d) and Windows95(trademark).
For the implementation of the present invention, a software application could be written in substantially any suitable programming language, which could easily be selected by one of ordinary skill in the art. The programming language chosen should be compatible with the computing platform according to which the software application is executed. Examples of suitable programming languages include, but are not limited to, C, C++ and Java.
In addition, the present invention could also be implemented as firmware or hardware. Hereinafter, the term xe2x80x9cfirmwarexe2x80x9d is defined as any combination of software and hardware, such as software instructions permanently burnt onto a ROM (read-only memory) device. As hardware, the present invention could be implemented as substantially any type of chip or other electronic device capable of performing the functions described herein.
In any case, the present invention can be described as a plurality of instructions being executed by a data processor, in which the data processor is understood to be implemented according to whether the present invention is implemented as software, hardware or firmware.
Hereinafter, the term xe2x80x9cWeb browserxe2x80x9d refers to any software program which can be used to view a document written at least partially with at least one instruction taken from HTML (HyperText Mark-up Language) or VRML (Virtual Reality Modeling Language), or any other equivalent computer document language, hereinafter collectively and generally referred to as xe2x80x9cdocument mark-up languagexe2x80x9d. Examples of Web browsers include, but are not limited to, Mosaic(trademark), Netscape Navigator(trademark) and Microsoft(trademark) Internet Explorer(trademark).
In order to teach various types of data networks, Data Networks is herein incorporated by reference (Bertsekas D. and Gallager R., Data Networks, 2nd ed. Englewood Cliffs, N.J.: Prentice Hall, 1992).